<?php
/**
 * 题目：树的子结构
 * 描述：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
 * 
 */

class TreeNode{
    public $val;
    public $left = null;
    public $right = null;
    public function __construct($val){
        $this->val = $val;
    }
}

/** 
 * 先序遍历父树
 * @param [type] $pRoot1 [description]
 * @param [type] $pRoot2 [description]
 */
function HasSubtree($pRoot1, $pRoot2)
{
	$result = false;
    if ($pRoot1 != null && $pRoot2 != null) {
    	if ($pRoot1->val == $pRoot2->val) {
    		$result = doesTree1HaveTree($pRoot1, $pRoot2);
    	}
    	if (!$result) {
	    	$result = HasSubtree($pRoot1->left, $pRoot2);
    	}
    	if (!$result) {
    		$result = HasSubtree($pRoot1->right, $pRoot2);
    	}
    }
   
    return $result;
}


function doesTree1HaveTree($node1, $node2) 
{
	if ($node2 == null) { // 子树遍历完了，则是父树的子树
		return true;
	}
	if ($node1 == null) { // 父树遍历完了 子树未完，则不是子树
		return false;
	}
	if ($node2->val != $node1->val) {
		return false;
	}
    //如果根节点对应的上，那么就分别去子节点里面匹配
	return doesTree1HaveTree($node1->left, $node2->left) && doesTree1HaveTree($node1->right, $node2->right);
}

$node = new TreeNode(1);
$node->left = new TreeNode(2);
$node->right = new TreeNode(3);

$node1 = new TreeNode(3);

echo HasSubtree($node, $node1);


